1. Field of Invention
The method and apparatus of the present invention relates to time division multiplexing and switching systems; specifically, it is a method and apparatus for establishing a plurality of communications channels embedded within a high speed transmission trunk by assigning fractional segments of the trunk's transmission capacity, called cell slots, to each of the channels to be established; more specifically, the method of the present invention creates a logical ordering of the set of cell slots within a predetermined time period called a frame, the logical ordering being reflective of each cell slot's assignment to one of the channels to be established, and then transforms the set of element addresses into a set of cell slot addresses which implicitly reflects each cell slot's logical assignment to a particular channel based on its physical position within the frame.
2. Description of the Related Art
A fundamental aspect of communications involves the establishment of a connection between one or more terminal devices and one or more other such devices. Early on, it was necessary to interconnect one telephone instrument with another so that two people could carry on a conversation. More recently, many different terminal devices are being interconnected, including computers, data and video terminals and many new types of voice terminals.
Facilitating the interconnection of one or more terminal devices with one or more other such devices requires a communication switching technique which may include a multicasting or conferencing capability. The characteristics of the requisite switching technique will vary with the application. At one extreme, one telephone is connected to one of a plurality of other telephones so that two people can hold a conversation. At the other extreme, one or more terminals will broadcast information to or collect information from a multiplicity of other terminals; broadcast radio and television (including both over-the-airwaves and cable systems) and telephone conferencing systems are examples. In the first case, switching equipment specifically designed for interconnecting telephones is used. In the broadcast case, a customer typically switches manually between channels that are all broadcast simultaneously to his terminal (i.e. a radio or television set). In the conferencing case, special equipment provides the requisite functionality. In all of these applications, a switching system selectively connects one or more terminals with one or more other terminals.
Switching systems have evolved from being totally mechanical to being electronic; the latter have been facilitated by the development in the 1960's of time division multiplexing techniques. A time division multiplexing system permits the sharing of a communication medium (typically a serial high speed trunk) among a number of conversations (conversations that may comprise voice, video or data information, or combinations thereof). To each of the users engaged in a particular one of the conversations, the serial communications medium can be made to appear exclusively dedicated to that specific conversation. For example, if there are three conversations labeled A, B, and C, the communication medium is devoted exclusively to each conversation for short periods of time. That is, a short segment from conversation A is followed by one from B followed by one from C and followed again by one from A, and so on.
Each of the interleaved conversations are said to be carried over one of a plurality of channels embedded in the communications medium. These embedded channels are not physically distinct transmission lines. Rather, they are partitions of the overall transmission capacity of the communications medium. Embedded channels define a plurality of subpaths comprising the high speed trunk, each of which carries data generated by different information sources to one or more destinations or data sinks. Thus, a time division multiplexed stream of information is a sequence of individual units of data, each uniquely associated with its respective data source(s) and sink(s), and transmitted over a communications medium in an interleaved fashion.
One of the principal requirements of any time division multiplexing system is the ability to associate each individual unit of data in the stream with the specific channel dedicated to connecting its source(s) to its destination(s). Typically this is accomplished by dividing the information transmission capacity of the communications medium into segments of time into which the individual units of data are embedded. Therefore, there must be a means for uniquely identifying each time segment with a specific channel that connects source(s) of data to destination terminal(s) and to see to it that only units of data from such source(s) are embedded within those time segments so identified.
In modern terminology, each time division segment comprising the transmission capacity of a communications medium is called a cell slot. Each unit of data embedded within a cell slot and which makes up part of the transmitted stream of information is often referred to as a cell. A cell may comprise one or more binary bits or a sample of an analog signal. Each cell slot is of a fixed time duration that is dependent upon characteristics of the system such as the size of a cell and the data transmission rate over the communications medium. The stream of cell slots are divided into frames, each comprising a predetermined number of cell slots. In typical time division multiplexing and switching systems, each of the information cells produced by the one or more sources is embedded into a unique one of the stream of cell slots (also known as time slots). Associated with each cell or cell slot is a channel identifier called a channel address, which identifies for the receiving end of the system to which channel the cell or cell slot belongs. Channel addresses can be either explicit or implicit. An explicit address is one where the channel identifier physically comprises part of the cell with which it is associated. An implicit address is one where the channel identifier is implicitly associated with a cell as a function of the unique position, within a frame, of the cell slot in which the cell is embedded. Each cell slot position within the frame is assigned to identify a particular channel based on some predefined convention. Each multiplexing termination at the source and receiving ends of a time division multiplexed trunk must therefore be constrained to the same predefined convention.
FIGS. 1a and 1b are illustrations of the two types of addressing noted above. FIG. 1a shows an explicit addressing example while FIG. 1b shows an implicit case. In the explicit example of FIG. 1a, the contents of each Cell Slot 1 is composed of two parts, an Address Portion 2, such as .alpha..sub.A, and a Payload Portion 11, such as A. In the implicit addressing case, each Cell Slot 4 contains only a payload portion. As noted above, the channel to which a particular cell slot is assigned is implicitly connoted by the cell slot's location in time (i.e. its physical location within a frame). Thus, the multiplexing devices associated with the communication system must be coordinated in accordance with some predefined convention to identify each cell slot with a particular channel. In typical systems employing implicit addressing, the convention or algorithm is fixed and therefore cannot be easily altered, especially during system operation.
Systems based on explicit addressing are called asynchronous time division multiplexing (ATDM) systems. They are asynchronous because the cells in ATDM systems have their channel addresses attached (see FIG. 1a) and therefore are not position referenced for purposes of identifying the channel to which the cell slot in which they are embedded belongs. Those systems based on implicit addressing are called synchronous time division multiplexing (STDM) systems. They are synchronous so that the sending and receiving multiplexers have the same frame of reference for identifying the channel to which each cell slot belongs based on its unique position in time.
In certain contexts, it is an advantage that explicit addressing ATDM systems can send cells at any time and therefore in any order, while in STDM systems, cells must be sent synchronously and therefore in a predetermined order. The arbitrary ordering that is the essence of ATDM has been the subject of much research and system implementation over the past 25 years or so. The history of these efforts has been well chronicled in a paper by A. G. Fraser, "Early Experiments with Asynchronous Time Division Networks", IEEE Network, Vol. 7, no. 1, pp. 12-26, (January 1993) incorporated herein by reference.
ATDM systems have been developed primarily for their advantageous application to data communications. The asynchronous character of ATDM is well suited to deal with the so-called bursty nature of data transmissions. Typically in data communication applications, the need for sending information occurs sporadically, in bursts. When a particular source wants to transmit information, it is often desirable to send it quickly. Thus, there is need for adequate communication channel transmission capacity on demand. Between the data bursts generated by a source, however, there is no reason to allocate trunk capacity to the channel over which that source is assigned to transmit. In conventional STDM circuit switching systems, trunk capacity is allocated up front for each channel through establishment of a physical circuit; a channel handling bursty data is therefore idle between bursts. This results in inefficient utilization of overall trunk transmission capacity.
The desire to achieve more efficient use of trunk capacity by STDM systems operating in the bursty data transmission context has led to the notion that a high capacity communication trunk could be shared among data communication sources (and thus channels) on a statistical basis. This idea rests on the assumption that the probability of more than a limited number of the total number of data communication sources will have data to send at the same time is small. Thus, even if the sum of the desired peak transmission rates from the data communication sources exceeds the total capacity of the communication trunk, the probability is high that there will be enough trunk capacity to handle the actual load at any given time. This will be true if the average load to be sent from the data communication sources is less than trunk capacity. In practical applications, however, delays for individual users continue to occur unless the average load is substantially less than the total trunk capacity.
ATDM techniques have thus become the de facto method of designing and building high speed multiplexing and switching systems. Devices currently in the market include statistical multiplexers and packet switches, designed for data traffic. Newer Asynchronous Transfer Mode (ATM) switches are being implemented as a part of Broadband Integrated Services Digital Networks (B-ISDN) as well as local network switches.
Another one of the advantages of ATDM technology over known STDM technology is its ability to support virtual circuits. A virtual circuit is a circuit (a connection between one or more signal sources and one or more signal sinks, which are involved in a specific conversation, via a communications medium) that has been established logically within a network, but is not physically connected until a sending terminal has information to transmit. The advantage of a virtual circuit is that the call establishment phase of implementing a network connection is performed only once. Thus, although trunk transmission capacity has not yet been physically allocated, the logisitics of establishing such a connection have already been put in place such that the physical connections necessary to permit transmission over the trunk can be made quickly when necessary. This establishes a physical route over the trunk which does not waste channel capacity when not needed and which maintains a high probability that sufficient capacity will exist when information must be transmitted. As previously mentioned, typical STDM systems are not suited to establishing virtual circuits because they have heretofore required an initial assignment of cell slots to channels as a matter of convention which, once established, is not easily altered during operation.
Although there has been great emphasis on ATDM technology, it possesses a number of significant disadvantages:
(a) As can be seen from FIG. 1a, explicit addressing demands that some of the communication trunk capacity be devoted to addressing, resulting in wasted capacity that cannot be allocated to information transmission. PA1 (b) Because of the required addressing overhead, a tradeoff must be made between the amount of channel capacity devoted to address information versus payload information. It is desirable to minimize the relative amount of capacity devoted to addressing. The payload portion of the cell must therefore be made large compared to the address portion to accomplish this. Unless the cell size is fixed, additional overhead is required to designate the length of each cell (as is done in most packet switching systems such as Frame Relay networks). This is one reason that newer cell-switching networks, including ATM and Switched Multimegabit Data Service (SMDS) make use of fixed cell sizes. PA1 (c) The minimum size of the address portion of a cell is determined by two factors: (1) the total number of terminals that might be connected (and their addresses) or (2) by the smallest number of virtual and real circuits that need be connected on a link simultaneously. For very large networks, such as the international public digital network, the number of addresses required greatly exceeds those needed to designate individual circuits on a multiplexed link. Therefore, a choice has been made for services such as ATM that limits the length of the address field to the anticipated maximum number of simultaneous link connections. This choice, while improving utilization efficiency of trunk capacity, increases the complexity of a network since each channel address must be mapped on a link by link basis to global network addresses. PA1 (d) If a communication error occurs during transmission of the address portion of a cell, a switching node cannot deliver the payload to the proper destination. To help overcome this problem, a certain amount of the transmission capacity is also devoted to error detection; the result is a further increase in overhead. (For example, ATM has standardized on a cell size of 53 bytes (424 bits) of which 48 bytes (384 bits) are payload data, 4 bytes (32 bits) are address information, and 1 byte (8 bits) is devoted to error detection). PA1 (e) Channel error rate has a profound effect on ATDM systems depending on the nature of the applications. In data applications, an error in transmitting a cell from a source to a sink can be detected by the application and a request for re-transmission can be sent to the source. This approach is tolerable because data transfers are usually not extremely time dependent. For most non-data applications, however, re-transmission schemes potentialy insert delays that can be intolerably large and variable. An error in the header portion of a cell is particularly disastrous because switching nodes cannot determine the destination of the cell requiring that the cell's entire contents be dropped. This characteristic of cell based systems necessitates very low error rate transmission facilities with their attendent high costs and low reliability. PA1 (f) It is desirable to keep the overall cell size small because larger cell sizes increase buffering requirements at switching nodes. Buffer storage results in transport delay through a switch node that can seriously degrade communication service where total communication trunk capacity is limited. For example, ATM results in small delays if communication facilities of the order of 45 megabits per second (Mbps) or more are used. At lower rates, the delay can limit interactive communication efficiency. Further, as cell size increases, the amount of buffering increases which leads to larger buffers consuming greater power and chip area. Finally, buffers must be managed to prioritize data traffic which increases control complexity. PA1 (g) In an integrated network that is devoted to voice and video communication along with data, most of the trunk capacity typically must be devoted to voice and video. These services are isochronous in nature; they send information at a fixed clocking rate that can endure for extended periods of time. They are not "bursty" information sources such as those found in data communications applications. To accommodate isochronous channels, ATDM networks require complex clocking subsystems. PA1 (h) Multicasting and conferencing can be accomplished by replicating cells or by defining "group addresses" that are interpreted at each node to define one or more destinations. Both approaches require complex manipulation of channel addresses. In conventional voice and data communication applications, multicasting and conferencing are fringe services. For video and multimedia applications, however, the ability to support multicasting becomes a much more important network requitement. PA1 (a) Circuit and trunk speeds are constrained to conform to the digital time multiplexing hierarchy standards that have been established by national and international standards organizations. Even though the standards facilitate interworking between equipment of different manufacturers and between different countries, the number of speeds is limited and they are extremely inflexible during system operation. PA1 (b) Current STDM switching systems have complex signaling systems that require large amounts of information to be transmitted to establish circuit connections. PA1 (c) Current STDM architectures require hierarchical physical structures that are cumbersome and expensive. PA1 (d) Almost all switching systems are constrained to minimum data rates of 64,000 bits per second (bps) and to, at most, integer multiples thereof. PA1 (e) Buffer memory amounting to one or more bytes per multiplex frame are required. PA1 (f) Switch transport delays of several milliseconds are common even though standard frame lengths are 125 microseconds (.mu.sec). PA1 (g) Providing virtual switched circuits is not practical with existing architectures. PA1 (h) Providing multicasting and conferencing are not inherently a pan of STDM switching systems. They are add-on modules and subsystems that must be provisioned separately. PA1 a) to provide time division multiplexing and switching where the cell size can be as small as desired, down to even a single bit or analog signal sample; PA1 b) to provide an addressing technique that can be communicated from a sending to a receiving multiplex station with small message sizes; PA1 c) to provide "bandwidth on demand" switching where an individual channel can be any integer multiple of some minimum rate such as 800 or 8,000 bits per second; PA1 d) to provide a means of channel allocation that utilizes trunk transmission capacity more efficiently than current practice; PA1 e) to provide the equivalent of statistical multiplexing without requiring the use of large buffers within switch nodes; PA1 f) to rapidly change the mix of embedded channels subdividing the transmission capacity of a high speed trunk; PA1 g) assigning cells to a channel so that the cells are nearly uniformly spaced in time and/or space within some frame of reference, limiting input and output buffer sizes to only a few bits or cells in length; PA1 h) to minimize transport delays through a multiplexing or switching node to only a few cell periods as measured at the nominal transmission rate of a switched channel; PA1 i) to provide the foundation for a network architecture that will support virtual circuits in an STDM environment; PA1 j) to provide a mechanism that will multiplex signals in both space and time, causing cell slots to appear in a deterministic order; PA1 k) to provide an information transport mechanism that, after an initial connection is made, does not mis-route information even when transmission errors occur; PA1 l) to provide for multicasting as an indigenous part of multiplexers and switches; and PA1 m) to provide for aggregation of signals at tandem nodes that can become a part of a conferencing system.
STDM systems do not exhibit these disadvantages. In particular, they do not confront the designer with the delay, congestion and clocking problems of ATDM systems. All known STDM systems do, however, exhibit one or more of the following disadvantages:
Thus, there is a need in the art for systems which can combine the advantages of ATDM systems such as their ability to reallocate channel capacity during real time operation in response to bursty data sources (i.e. through the use of virtual circuits and "bandwidth on demand"), with the advantages of STDM systems such as their ability to minimize transmission capacity overhead through implicit channel addressing.